{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Using a Robot to Print the Lexicographically Smallest String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: robotWithString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使用机器人打印字典序最小的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;和一个机器人，机器人当前有一个空字符串&nbsp;<code>t</code>&nbsp;。执行以下操作之一，直到&nbsp;<code>s</code> 和&nbsp;<code>t</code>&nbsp;<strong>都变成空字符串：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>删除字符串&nbsp;<code>s</code>&nbsp;的 <strong>第一个</strong>&nbsp;字符，并将该字符给机器人。机器人把这个字符添加到 <code>t</code>&nbsp;的尾部。</li>\n",
    "\t<li>删除字符串&nbsp;<code>t</code>&nbsp;的&nbsp;<strong>最后一个</strong>&nbsp;字符，并将该字符给机器人。机器人将该字符写到纸上。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回纸上能写出的字典序最小的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"zza\"\n",
    "<b>输出：</b>\"azz\"\n",
    "<b>解释：</b>用 p 表示写出来的字符串。\n",
    "一开始，p=\"\" ，s=\"zza\" ，t=\"\" 。\n",
    "执行第一个操作三次，得到 p=\"\" ，s=\"\" ，t=\"zza\" 。\n",
    "执行第二个操作三次，得到 p=\"azz\" ，s=\"\" ，t=\"\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"bac\"\n",
    "<b>输出：</b>\"abc\"\n",
    "<b>解释：</b>用 p 表示写出来的字符串。\n",
    "执行第一个操作两次，得到 p=\"\" ，s=\"c\" ，t=\"ba\" 。\n",
    "执行第二个操作两次，得到 p=\"ab\" ，s=\"c\" ，t=\"\" 。\n",
    "执行第一个操作，得到 p=\"ab\" ，s=\"\" ，t=\"c\" 。\n",
    "执行第二个操作，得到 p=\"abc\" ，s=\"\" ，t=\"\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"bdda\"\n",
    "<b>输出：</b>\"addb\"\n",
    "<b>解释：</b>用 p 表示写出来的字符串。\n",
    "一开始，p=\"\" ，s=\"bdda\" ，t=\"\" 。\n",
    "执行第一个操作四次，得到 p=\"\" ，s=\"\" ，t=\"bdda\" 。\n",
    "执行第二个操作四次，得到 p=\"addb\" ，s=\"\" ，t=\"\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [using-a-robot-to-print-the-lexicographically-smallest-string](https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [using-a-robot-to-print-the-lexicographically-smallest-string](https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"zza\"', '\"bac\"', '\"bdda\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        a = [0] * 26\n",
    "        for x in s: a[ord(x) - 97] += 1\n",
    "\n",
    "        t = []\n",
    "        ss = ''\n",
    "        for x in s:\n",
    "            a[ord(x) - ord('a')] -= 1\n",
    "            t.append(x)\n",
    "            while t and sum(a[:ord(t[-1]) - 97]) == 0:\n",
    "                ss += t.pop()\n",
    "\n",
    "        return ss + ''.join(t[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n=len(s)\n",
    "        d=collections.deque([n-1])\n",
    "        ans=''\n",
    "        tt=[]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            if s[i]<=s[d[0]]:\n",
    "                d.appendleft(i)\n",
    "            else:\n",
    "                d.appendleft(d[0])\n",
    "        p=-1\n",
    "        while p!=n-1:\n",
    "            x=d[p+1]\n",
    "            while tt and tt[-1]<=s[x]:\n",
    "                ans+=tt.pop()\n",
    "\n",
    "\n",
    "            ans+=s[x]\n",
    "            for i in range(p+1,x):\n",
    "                tt.append(s[i])\n",
    "            p=d[p+1]\n",
    "        while tt:\n",
    "            ans+=tt.pop()\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        mn = 0\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while mn < 25 and cnt[ascii_lowercase[mn]] == 0:\n",
    "                mn += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[mn]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        mapping = [0]*26\n",
    "        for c in s:\n",
    "            mapping[ord(c)-ord('a')] += 1\n",
    "        def check(c):\n",
    "            for i in range(ord(c)-ord('a')-1,-1,-1):\n",
    "                if(mapping[i] > 0):\n",
    "                    return True\n",
    "            return False\n",
    "        result = ''\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if(check(c)):\n",
    "                st.append(c)\n",
    "            else:\n",
    "                result += c \n",
    "            mapping[ord(c)-ord('a')] -= 1\n",
    "            while(st and not check(st[-1])):\n",
    "                result += st.pop()\n",
    "            \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        c = Counter(s)\n",
    "        min = 0\n",
    "        st = list()\n",
    "        ans = list()\n",
    "        for i in s:\n",
    "            c[i] -= 1\n",
    "            while min < 25 and c[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(i)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        mapping = [0]*26\n",
    "        for c in s:\n",
    "            mapping[ord(c)-ord('a')] += 1\n",
    "        def check(c):\n",
    "            for i in range(ord(c)-ord('a')-1,-1,-1):\n",
    "                if(mapping[i] > 0):\n",
    "                    return True\n",
    "            return False\n",
    "        result = ''\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if(check(c)):\n",
    "                st.append(c)\n",
    "            else:\n",
    "                result += c \n",
    "            mapping[ord(c)-ord('a')] -= 1\n",
    "            while(st and not check(st[-1])):\n",
    "                result += st.pop()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ss = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\"\n",
    "        ans = \"\"\n",
    "        cnt = Counter(s)\n",
    "        min = 0  \n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            st.append(c)\n",
    "            while min < 51 and cnt[ss[min]] == 0:\n",
    "                min += 1\n",
    "            while st and st[-1] <= ss[min]:\n",
    "                ans += st.pop()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        seen = [0]*26\n",
    "        ans = \"\"\n",
    "        for x in s:\n",
    "            seen[ord(x)-ord('a')]+=1\n",
    "        minn = 0\n",
    "        n = len(s)\n",
    "        l = -1\n",
    "        had = [False]*n\n",
    "        for i in range(n):\n",
    "            while minn < 25 and seen[minn] == 0:\n",
    "                minn += 1\n",
    "            while l>=0 and ord('a')+minn>=ord(s[l]):\n",
    "                if  not had[l]:\n",
    "                    ans += s[l]\n",
    "                    had[l] = True\n",
    "                l-=1\n",
    "            if ord('a')+minn==ord(s[i]):\n",
    "                ans += s[i]\n",
    "                l = i\n",
    "                had[l] = True\n",
    "            seen[ord(s[i])-ord('a')] -= 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not had[i]:\n",
    "                ans += s[i]\n",
    "        del seen \n",
    "        del had\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        seen = [0]*26\n",
    "        ans = \"\"\n",
    "        for x in s:\n",
    "            seen[ord(x)-ord('a')]+=1\n",
    "        minn = 0\n",
    "        n = len(s)\n",
    "        l = -1\n",
    "        had = [False]*n\n",
    "        for i in range(n):\n",
    "            while minn < 25 and seen[minn] == 0:\n",
    "                minn += 1\n",
    "            while l>=0 and ord('a')+minn>=ord(s[l]):\n",
    "                if  not had[l]:\n",
    "                    ans += s[l]\n",
    "                    had[l] = True\n",
    "                l-=1\n",
    "            if ord('a')+minn==ord(s[i]):\n",
    "                ans += s[i]\n",
    "                l = i\n",
    "                had[l] = True\n",
    "            seen[ord(s[i])-ord('a')] -= 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not had[i]:\n",
    "                ans += s[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        mapping = [0]*26\n",
    "        for c in s:\n",
    "            mapping[ord(c)-ord('a')] += 1\n",
    "        def check(c):\n",
    "            for i in range(ord(c)-ord('a')-1,-1,-1):\n",
    "                if(mapping[i] > 0):\n",
    "                    return True\n",
    "            return False\n",
    "        result = ''\n",
    "        st = []\n",
    "        for c in s:\n",
    "            if(check(c)):\n",
    "                st.append(c)\n",
    "            else:\n",
    "                result += c \n",
    "            mapping[ord(c)-ord('a')] -= 1\n",
    "            while(st and not check(st[-1])):\n",
    "                result += st.pop()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ss = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\"\n",
    "        ans = \"\"\n",
    "        cnt = Counter(s)\n",
    "        M = 0  \n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            st.append(c)\n",
    "            while M < 51 and cnt[ss[M]] == 0:\n",
    "                M += 1\n",
    "            while st and st[-1] <= ss[M]:\n",
    "                ans += st.pop()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        t = []\n",
    "        ans = ''\n",
    "        tmp = 'A'\n",
    "        n = len(s)\n",
    "        cnt = Counter()\n",
    "        for i in range(n):\n",
    "            o = ord(s[i])\n",
    "            cnt[o]+=1\n",
    "        l = [kk for kk in cnt.keys()]\n",
    "        l.sort()\n",
    "        for i in range(n):\n",
    "            o = ord(s[i])\n",
    "            if o==l[0]:\n",
    "                ans = ans + s[i]\n",
    "                cnt[o]-=1\n",
    "                if cnt[o]==0:\n",
    "                    l.pop(0)\n",
    "            else:\n",
    "                t.append(s[i])\n",
    "                cnt[ord(s[i])]-=1\n",
    "                if cnt[ord(s[i])]==0:\n",
    "                    idx = l.index(ord(s[i]))\n",
    "                    l.pop(idx)\n",
    "            while t!=[]:\n",
    "                if l == []:\n",
    "                    break\n",
    "                if ord(t[-1])<=l[0]:\n",
    "                    ans = ans + t[-1]\n",
    "                    t.pop()\n",
    "                else:\n",
    "                    break\n",
    "        while len(t)!=0:\n",
    "            ans = ans + t.pop()\n",
    "        return ans\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ss = \"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz\"\n",
    "        ans = \"\"\n",
    "        cnt = Counter(s)\n",
    "        M = 0  \n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            st.append(c)\n",
    "            while M < 51 and cnt[ss[M]] == 0:\n",
    "                M += 1\n",
    "            while st and st[-1] <= ss[M]:\n",
    "                ans += st.pop()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=2434 lang=python3\n",
    "#\n",
    "# [2434] 使用机器人打印字典序最小的字符串\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        # 考虑当前的字符，判断是不是最小的，如果是最小的\n",
    "        # 直接输出即可，如果不是找到最小的则找到最小的为止\n",
    "        cnt = [0] * 26\n",
    "        for c in s:\n",
    "            cnt[ord(c) - ord('a')] += 1\n",
    "        l, r = 0, 0 \n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        stk = []\n",
    "        for i, c in enumerate(cnt):\n",
    "            while stk and (ord(stk[-1]) - ord('a')) <= i:\n",
    "                ans.append(stk[-1])\n",
    "                stk.pop()\n",
    "            while r < n and cnt[i] != 0:\n",
    "                idx = ord(s[r]) - ord('a')\n",
    "                if idx == i:\n",
    "                    ans.append(s[r])\n",
    "                else:\n",
    "                    stk.append(s[r])\n",
    "                cnt[idx] -= 1\n",
    "                r += 1\n",
    "            # print(stk)\n",
    "            while stk and (ord(stk[-1]) - ord('a')) <= i:\n",
    "                ans.append(stk[-1])\n",
    "                stk.pop()\n",
    "        return \"\".join(ans)\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        stack = []\n",
    "        ans = []\n",
    "        for i, ch in enumerate(s):\n",
    "            stack.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "            while stack and not any(k < stack[-1] and v > 0 for k, v in cnt.items()):\n",
    "                ans.append(stack.pop())\n",
    "\n",
    "        while stack:\n",
    "            ans.append(stack.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)\n",
    "\n",
    "s = Solution()\n",
    "s.robotWithString(\"bac\")\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        t,locs,st,ans = 0,dict(),[],[]\n",
    "        \n",
    "        for i,c in enumerate(s): locs[c] = i\n",
    "\n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            while st and st[-1] <= c: ans.append(st.pop())\n",
    "            if c not in locs: continue\n",
    "            while t <= locs[c]:\n",
    "                if s[t] == c: ans.append(c)\n",
    "                else: st.append(s[t])\n",
    "                t += 1\n",
    "        \n",
    "        while st: ans.append(st.pop())\n",
    "\n",
    "        return ''.join(ans)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        minv = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while minv < 25 and cnt[ascii_lowercase[minv]] == 0:\n",
    "                minv += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[minv]: ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        stk = []\n",
    "        mi = 'a'\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while mi < 'z' and cnt[mi] == 0:\n",
    "                mi = chr(ord(mi) + 1)\n",
    "            stk.append(c)\n",
    "            while stk and stk[-1] <= mi:\n",
    "                ans.append(stk.pop())\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        mn = 0\n",
    "        t = []\n",
    "        a = 'abcdefghijklmnopqrstuvwxyz'\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while mn < 25 and cnt[a[mn]] == 0:\n",
    "                mn += 1\n",
    "            t.append(c)\n",
    "            while t and t[-1] <= a[mn]:\n",
    "                ans.append(t.pop(-1))\n",
    "        return ''.join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def counter(string: str) -> dict:\n",
    "    hashtable = dict()\n",
    "    for i in range(97, 123, 1):\n",
    "        hashtable[chr(i)] = 0\n",
    "    for item in string:\n",
    "        hashtable[item] += 1\n",
    "    return hashtable\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        t = []\n",
    "        ans = []\n",
    "        mn = counter(s)\n",
    "        a_ascii = 97\n",
    "        while mn[chr(a_ascii)] == 0:\n",
    "            a_ascii += 1\n",
    "        for item in s:\n",
    "            if item == chr(a_ascii):  # 等于就写纸上\n",
    "                ans.append(item)\n",
    "                mn[item] -= 1\n",
    "                while True:  # 还得同时找到下一个贪心目标并且观察栈顶\n",
    "                    while a_ascii < 123 and mn[chr(a_ascii)] == 0:\n",
    "                        a_ascii += 1\n",
    "                    if t and t[-1] <= chr(a_ascii):  # 栈顶入栈\n",
    "                        mn[t[-1]] -= 1\n",
    "                        ans.append(t.pop())\n",
    "                        if t:\n",
    "                            mn[t[-1]] += 1\n",
    "                    else:  # 直到不同才弹出\n",
    "                        break\n",
    "            else:  # 不等于就入栈\n",
    "                t.append(item)\n",
    "                if len(t) > 1:\n",
    "                    mn[t[-2]] -= 1\n",
    "        while t:\n",
    "            ans.append(t.pop())\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        stack = []\n",
    "        ans = []\n",
    "        minn = 0\n",
    "        for ch in s:\n",
    "            stack.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "            while minn < 25 and cnt[chr(minn + 97)] <= 0:\n",
    "                minn += 1\n",
    "            while stack and stack[-1] <= chr(minn + 97):\n",
    "                ans.append(stack.pop())\n",
    "            \n",
    "        while stack:\n",
    "            ans.append(stack.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while  st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 贪心 + 栈\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "\n",
    "        cnts = Counter(s)\n",
    "        st = []\n",
    "        mn = 0\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            cnts[c] -= 1\n",
    "            while mn < 25 and cnts[ascii_lowercase[mn]] == 0: # mn < 25，防止ascii_lowercase使用下标访问时越界\n",
    "                mn += 1\n",
    "            st.append(c)\n",
    "            # print(st, c)\n",
    "            while st and st[-1] <= ascii_lowercase[mn]:\n",
    "                ans.append(st.pop())\n",
    "\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ans = \"\"\n",
    "        post = [\"z\"]*n\n",
    "        post[-1]  = s[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            post[i] = min(post[i+1], s[i])\n",
    "        i = 0\n",
    "        t = []\n",
    "        while i < n:\n",
    "            if not t or post[i] < t[-1]:\n",
    "                t.append(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += t.pop()\n",
    "        ans += \"\".join(t)[::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        min = 0  # 剩余最小字母\n",
    "        st = []\n",
    "        for c in s:\n",
    "            cnt[c] -= 1\n",
    "            while min < 25 and cnt[ascii_lowercase[min]] == 0:\n",
    "                min += 1\n",
    "            st.append(c)\n",
    "            while st and st[-1] <= ascii_lowercase[min]:\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        ls = []\n",
    "        f = [0] * (n+1)\n",
    "        f[n] = ord('z') + 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            f[i] = min(f[i+1], ord(s[i]))\n",
    "\n",
    "        r = []\n",
    "        res = \"\"\n",
    "        for i, c in enumerate(s):\n",
    "            r.append(c)\n",
    "            while len(r) and ord(r[-1]) <= f[i+1]:\n",
    "                res += r.pop()\n",
    "        return res + \"\".join(r)[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ls = len(s)\n",
    "        minchr = [''] * ls\n",
    "        minchr[-1] = s[-1]\n",
    "        for i in range(ls - 2, -1, -1):\n",
    "            minchr[i] = min(s[i], minchr[i + 1])\n",
    "        ans = ''\n",
    "        i = 1\n",
    "        t = [s[0]]\n",
    "        while i < ls:\n",
    "            if not t or t[-1] > minchr[i]:\n",
    "                t.append(s[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += t.pop()\n",
    "        if t:\n",
    "            ans += ''.join(t[::-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ss, t = '', []\n",
    "        while s:\n",
    "            c = min(s)\n",
    "            while t and t[-1] <= c:\n",
    "                ss += t.pop()\n",
    "            k = s.rfind(c)\n",
    "            ss += c * s.count(c)\n",
    "            t += list(s[:k].replace(c, ''))\n",
    "            s = s[k + 1:]\n",
    "        ss += ''.join(t[::-1])\n",
    "        return ss\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        right = [' ' for _ in range(n + 1)]\n",
    "        right[n] = chr(ord('z') + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            right[i] = min(s[i], right[i + 1])\n",
    "        \n",
    "        res = []\n",
    "        stk = collections.deque()\n",
    "        for i, c in enumerate(s):\n",
    "            stk.append(c)\n",
    "            while stk and stk[-1] <= right[i + 1]:\n",
    "                res.append(stk.pop())\n",
    "        \n",
    "        return ''.join(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        temp = ['z']\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if not temp or s[i] < temp[-1]: temp.append(s[i])\n",
    "            else: temp.append(temp[-1])\n",
    "        temp = temp[::-1]\n",
    "\n",
    "        res = []\n",
    "        stack  = []\n",
    "        for j, ch in enumerate(s):\n",
    "            stack.append(ch)\n",
    "            while stack and stack[-1] <= temp[j+1]:\n",
    "                res.append(stack.pop())\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        st = []\n",
    "        for ch in s:\n",
    "            while st and all(cnt[chr(x)] == 0 for x in range(ord('a'), ord(st[-1]))):\n",
    "                ans.append(st.pop())\n",
    "            st.append(ch)\n",
    "            cnt[ch] -= 1\n",
    "        ans += st[::-1]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        ans = []\n",
    "        st = []\n",
    "        cnt = [0] * 26\n",
    "        for c in s: cnt[ord(c)-ord('a')] += 1\n",
    "        for c in s:\n",
    "            x = ord(c)-ord('a')\n",
    "            cnt[x] -= 1\n",
    "            for y in range(26):\n",
    "                if cnt[y] != 0: break\n",
    "            st.append(x)\n",
    "            while st and st[-1] <= y: ans.append(st.pop())\n",
    "        while st: ans.append(st.pop())\n",
    "        return ''.join(map(lambda x:chr(ord('a')+x),ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        # 1先找到最小的元素，这个元素一定是第一个弹出，弹出后如果栈顶是剩余元素最小则弹出，如果最小和慈孝有元素，因为是站不可能越过中间元素先弹出b在弹出c,所以只要当前元素是为便利的最小就弹出，如果栈顶是最小就循环弹出，知道栈空或者栈顶元素大于为便利最小，那么要先弹出为便利最小来获得字典序最小字符串 \n",
    "        # 如果当前是c,c入栈，如果stack[-1]<=m，那么栈顶弹出，因为不弹出 不会得到更好结果\n",
    "        # 如果c>m，那么要等更小元素入栈在弹出相应元素才会的到最小\n",
    "        # f[i]表示s[i]之后最小的元素\n",
    "        n = len(s)\n",
    "        f = ['z'] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if i == n - 1:\n",
    "                f[i] = s[i]\n",
    "            else:\n",
    "                f[i] = min(f[i + 1], s[i])\n",
    "        st = []\n",
    "        ans = []\n",
    "        for i, c in enumerate(s):\n",
    "            st.append(c)\n",
    "            while st and (i == n - 1 or i < n - 1 and st[-1] <= f[i + 1]):\n",
    "                ans.append(st.pop())\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        h = ['z'] * (len(s) + 1)\n",
    "        for i in range(len(s) - 1, -1, -1): h[i] = min(h[i + 1], s[i])\n",
    "\n",
    "        ss, t = '', []\n",
    "        for x, y in zip(s, h[1:]):\n",
    "            t.append(x)\n",
    "            while t and y >= t[-1]: ss += t.pop()\n",
    "\n",
    "        return ss + ''.join(t[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        h = list(s) + ['z']\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if h[i + 1] < h[i]:\n",
    "                h[i] = h[i + 1]\n",
    "\n",
    "        ss, t = '', []\n",
    "        for x, y in zip(s, h[1:]):\n",
    "            t.append(x)\n",
    "            while t and y >= t[-1]: ss += t.pop()\n",
    "\n",
    "        return ss + ''.join(t[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n = len(s)\n",
    "        least = [i for i in range(n)]\n",
    "        for i in reversed(range(n-1)):\n",
    "            if s[i] > s[least[i+1]]:\n",
    "                least[i] = least[i+1]\n",
    "        t, printed = [], []\n",
    "        i = 0\n",
    "        while True:\n",
    "            if t:\n",
    "                if i == n or t[-1] <= s[least[i]]:\n",
    "                    printed.append(t[-1])\n",
    "                    del t[-1]\n",
    "                else:\n",
    "                    k = least[i]\n",
    "                    while i < k:\n",
    "                        t.append(s[i])\n",
    "                        i += 1\n",
    "                    printed.append(s[k])\n",
    "                    i = k + 1\n",
    "            else:\n",
    "                if i < n:\n",
    "                    t.append(s[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "        return ''.join(printed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n,pre = len(s),-1\n",
    "        ans, vis, locs = [], [False]*n, defaultdict(list)\n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "\n",
    "        def jump(pre,c):\n",
    "            while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            return pre\n",
    "            \n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            pre = jump(pre,c)\n",
    "            # while pre >= 0 and (vis[pre] or s[pre] < c):\n",
    "            #     if not vis[pre]:\n",
    "            #         vis[pre] = True\n",
    "            #         ans.append(s[pre])\n",
    "            #     pre -= 1\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                if not vis[locs[c][i]]:\n",
    "                    ans.append(c)\n",
    "                    vis[locs[c][i]] = True\n",
    "                    pre = jump(locs[c][i]-1,c)\n",
    "                # pre = locs[c][i] - 1\n",
    "                # while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                #     if not vis[pre]:\n",
    "                #         vis[pre] = True\n",
    "                #         ans.append(s[pre])\n",
    "                #     pre -= 1\n",
    "                i += 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        locs = defaultdict(list)\n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        n = len(s)\n",
    "        vis = [False] * n\n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            while pre >= 0 and (vis[pre] or s[pre] < c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                ans.append(c)\n",
    "                vis[locs[c][i]] = True\n",
    "                pre = locs[c][i] - 1\n",
    "                while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                    if not vis[pre]:\n",
    "                        vis[pre] = True\n",
    "                        ans.append(s[pre])\n",
    "                    pre -= 1\n",
    "                i += 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n,pre = len(s),-1\n",
    "        ans, vis, locs = [], [False]*n, defaultdict(list)\n",
    "        \n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "\n",
    "        def jump(pre,c):\n",
    "            while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            return pre\n",
    "            \n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            pre = jump(pre,c)\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                if not vis[locs[c][i]]:\n",
    "                    ans.append(c)\n",
    "                    vis[locs[c][i]] = True\n",
    "                    # pre = jump(locs[c][i]-1,c)\n",
    "                    pre = locs[c][i]-1\n",
    "                i += 1\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n,pre = len(s),-1\n",
    "        ans, vis, locs = [], [False]*n, defaultdict(list)\n",
    "        \n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "\n",
    "        def jump(pre,c):\n",
    "            while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            return pre\n",
    "            \n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            pre = jump(pre,c)\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                if not vis[locs[c][i]]:\n",
    "                    ans.append(c)\n",
    "                    vis[locs[c][i]] = True\n",
    "                    pre = locs[c][i]-1\n",
    "                i += 1\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n,pre = len(s),-1\n",
    "        ans, vis, locs = [], [False]*n, defaultdict(list)\n",
    "        \n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "\n",
    "        def jump(pre,c):\n",
    "            while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            return pre\n",
    "            \n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            pre = jump(pre,c)\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                if not vis[locs[c][i]]:\n",
    "                    ans.append(c)\n",
    "                    vis[locs[c][i]] = True\n",
    "                    pre = jump(locs[c][i]-1,c)\n",
    "                i += 1\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        locs = defaultdict(list)\n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "        ans = []\n",
    "        pre = -1\n",
    "        n = len(s)\n",
    "        vis = [False] * n\n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            # while pre >= 0 and vis[pre]: pre -= 1\n",
    "            while pre >= 0 and (vis[pre] or s[pre] < c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                ans.append(c)\n",
    "                vis[locs[c][i]] = True\n",
    "                pre = locs[c][i]\n",
    "                while pre-1 >= 0 and (vis[pre-1] or s[pre-1] <= c):\n",
    "                    pre -= 1\n",
    "                    if vis[pre]: continue\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                i += 1\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        n,pre = len(s),-1\n",
    "        ans, vis, locs = [], [False]*n, defaultdict(list)\n",
    "        \n",
    "        for i,c in enumerate(s): locs[c].append(i)\n",
    "\n",
    "        def jump(pre,c):\n",
    "            while pre >= 0 and (vis[pre] or s[pre] <= c):\n",
    "                if not vis[pre]:\n",
    "                    vis[pre] = True\n",
    "                    ans.append(s[pre])\n",
    "                pre -= 1\n",
    "            return pre\n",
    "            \n",
    "        for x in range(26):\n",
    "            c = chr(ord('a') + x)\n",
    "            pre = jump(pre,c)\n",
    "            if c not in locs: continue\n",
    "            i = bisect_left(locs[c],pre)\n",
    "            while i < len(locs[c]):\n",
    "                if not vis[locs[c][i]]:\n",
    "                    ans.append(c)\n",
    "                    vis[locs[c][i]] = True\n",
    "                    pre = jump(locs[c][i]-1,c)\n",
    "                i += 1\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if not vis[i]: ans.append(s[i])\n",
    "        \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotWithString(self, s: str) -> str:\n",
    "        rights = deque(sorted((c, i) for i, c in enumerate(s)))\n",
    "        stack = []\n",
    "        off = -1\n",
    "        res = []\n",
    "        while True:\n",
    "            while rights and rights[0][1] <= off:\n",
    "                rights.popleft()\n",
    "            if not rights:\n",
    "                res.extend(reversed(stack))\n",
    "                return ''.join(res)\n",
    "            while stack and stack[-1] <= rights[0][0]:\n",
    "                res.append(stack.pop())\n",
    "            c, noff = rights.popleft()\n",
    "            stack.extend(s[off+1:noff])\n",
    "            off = noff\n",
    "            res.append(c)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
